// https://leetcode.cn/problems/sort-the-people/description/

// 算法思路总结：
// 1. 创建身高-姓名的配对向量
// 2. 按身高降序排序配对数据
// 3. 提取排序后的姓名组成结果向量
// 4. 时间复杂度：O(nlogn)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    typedef pair<int, string> PIS;
    vector<string> sortPeople(vector<string>& names, vector<int>& heights) 
    {
        int m = names.size();
        vector<PIS> pv;
        for (int i = 0 ; i < m ; i++)
            pv.push_back({heights[i], names[i]});
        
        sort(pv.begin(), pv.end(), [](const PIS& p1, const PIS& p2){
            return p1.first > p2.first;
        });

        vector<string> res;
        for (const auto& pair : pv)
            res.push_back(pair.second);
        
        return res;
    }
};

int main()
{
    vector<string> n1 = {"Mary","John","Emma"}, n2 = {"Alice","Bob","Bob"};
    vector<int> h1 = {180,165,170}, h2 = {155,185,150};
    Solution sol;

    auto r1 = sol.sortPeople(n1, h1);
    auto r2 = sol.sortPeople(n2, h2);

    for (const auto& str : r1)
        cout << str << " ";
    cout << endl;

    for (const auto& str : r2)
        cout << str << " ";
    cout << endl;


    return 0;
}